package swardToOffer.method_4_dp_or_greedy;

/**
 * @Author ChanZany
 * @Date 2021/5/25 8:52
 * @Version 1.0
 * <p>
 * 面试题46：把数字翻译成字符串
 * 题目：给定一个数字，我们按照如下规则把它翻译为字符串：0翻译成"a"，1翻
 * 译成"b"，……，11翻译成"l"，……，25翻译成"z"。一个数字可能有多个翻译。例
 * 如12258有5种不同的翻译，它们分别是"bccfi"、"bwfi"、"bczi"、"mcfi"和
 * "mzi"。请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
 * 分析:假设给定的数字为1002
 * 则从第一位开始,可以选择两种翻译方式,
 * 1.翻译"1",剩余n-1个数字待翻译
 * 2.翻译"10"(当10<=x<25),剩余n-2个数字待翻译
 * 我们使用动态规划来求解,首先设置状态为f(n),表示前n个数字所能得到的所有翻译方法
 * 那么可以得到f(n)=f(n-1)+f(n-2)[if 10<=a[n-1]|a[n]<=25]
 * 并且可以得到初始状态值为f(0)=f(1)=1,f(2)=f(1)+f(0)=2[若a[1]|a[2]在10~25范围内];
 * <p>
 * 空间优化,dp[i]只与dp[i-1]/dp[i-2]有关,所以通过滚动数组的方式对其进行优化
 * 使用三个变量保存a=dp[i], b=dp[i-1],c=dp[i-2]
 * 每次循环开始,a=b,a+=c(满足条件)
 * 每次循环结束,a -> b, b->c, 0->a
 */
public class TranslateNumbersToStrings {
    public int translateNumPro(int num) {
        char[] charArray = String.valueOf(num).toCharArray();
        int len = charArray.length;
        if (len < 2) return len;
        int b = 1, c = 1, a = 0;
        for (int i = 1; i < len; i++) {
            a = b; //取一个数字做翻译
            int tmp = 10 * (charArray[i - 1] - '0') + (charArray[i] - '0');
            if (tmp >= 10 && tmp <= 25) a += c; //取两个数字做翻译
            c = b;
            b = a;
        }
        return b;
    }

    public int translateNum(int num) {
        char[] charArray = String.valueOf(num).toCharArray();
        int len = charArray.length;
        if (len < 2) return len;
        int[] dp = new int[len + 1];
        dp[0] = dp[1] = 1;
        for (int i = 1; i < len; i++) {
            dp[i + 1] = dp[i]; //取一个数字做翻译
            int tmp = 10 * (charArray[i - 1] - '0') + (charArray[i] - '0');
            if (tmp >= 10 && tmp <= 25) dp[i + 1] += dp[i - 1]; //取两个数字做翻译
        }
        return dp[len];
    }

    public static void main(String[] args) {
        TranslateNumbersToStrings Main = new TranslateNumbersToStrings();
        System.out.println(Main.translateNumPro(12345));
    }
}
